import java.util.ArrayList;
import java.util.List;

/**
 * 1588. 所有奇数长度子数组的和
 * https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/
 */
public class Solutions_1588 {
    public static void main(String[] args) {
        int[] arr1 = {1, 4, 2, 5, 3};  // output: 58
        int[] arr2 = {1, 2};  // output: 3
        int[] arr3 = {10, 11, 12};  // output: 66

        List<int[]> inputs = new ArrayList<>();
        inputs.add(arr1);
        inputs.add(arr2);
        inputs.add(arr3);

        for (int[] input : inputs) {
            int result = sumOddLengthSubarrays(input);
            System.out.println(result);
        }
    }

    /**
     * 前缀和数组：preSum[1] = 5，表示 arr 数组中 [0, 1] 区间内的元素和为 5
     */
    public static int sumOddLengthSubarrays(int[] arr) {
        int len = arr.length;
        int[] preSum = new int[len];
        preSum[0] = arr[0];
        for (int i = 1; i < len; i++) {
            preSum[i] = arr[i] + preSum[i - 1];
        }
        int res = 0;
        for (int i = 1; i <= len; i += 2) {
            if (i == 1 || i == len) {
                res += preSum[len - 1];
                continue;
            }
            for (int j = i - 1; j < len; j++) {
                res += preSum[j];
                if (j - i >= 0) {
                    res -= preSum[j - i];
                }
            }
        }
        return res;
    }
}
